/* 两个递增有序的单链表，设计算法成一个非递增有序的链表 */
#include <iostream>
#include "headfun.h"
using namespace std;

// 合并两个链表
void fun(LNode *&A, LNode *&B)
{
  // 辅助指针
  LNode *p = A->next, *q = B->next, *s;
  
  // 临时置空
  A->next = NULL;
  B->next = NULL;
  
  // 遍历两个链表，直到其中一个遍历完毕
  while (p != NULL && q != NULL)
  {
    // A结点数值更小，头插法
    if (p->data <= q->data)
    {
      s = p;
      p = p->next;
      s->next = A->next;
      A->next = s;
    }
    
    // B结点数值更小，头插法
    else
    {
      s = q;
      q = q->next;
      s->next = A->next;
      A->next = s;
    }
  }
  
  // A没有遍历完毕，头插法
  while (p != NULL)
  {
    s = p;
    p = p->next;
    s->next = A->next;
    A->next = s;
  }
  
  // B没有遍历完毕， 头插法
  while (q != NULL)
  {
    s = q;
    q = q->next;
    s->next = A->next;
    A->next = s;
  }
}

int main()
{
  // 创建两个链表
  cout << " 链表A:";
  LNode *A = head_Linklist();
  cout << " 链表B:";
  LNode *B = head_Linklist();
  
  // 合并到链表A
  fun(A, B);
  
  // 打印信息
  LNode *q = A->next;
  cout << "合并之后的链表:";
  while (q != NULL)
  {
    cout << q->data << " ";
    q = q->next;
  }
  return 0;
}